package 力扣_树算法.二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**100.相同的树
 * @author zx
 * @create 2022-04-10 12:29
 */
public class Num100 {
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        /**
         * 也可以通过广度优先搜索判断两个二叉树是否相同。同样首先判断两个二叉树是否为空，如果两个二叉树都不为空，
         * 则从两个二叉树的根节点开始广度优先搜索。使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别
         * 加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作。
         * > 比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同；
         * > 如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，
         *   或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同；
         * > 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，
         *   子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。
         * > 如果搜索结束时两个队列同时为空，则两个二叉树相同。如果只有一个队列为空
         *   则两个二叉树的结构不同，因此两个二叉树不同。
         */
        if(p == null && q == null){
            return true;
        }else if(p == null || q == null){
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.add(p);
        queue2.add(q);
        while(!queue1.isEmpty() && !queue2.isEmpty()){
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if(node1.val != node2.val){
                return false;
            }
            // 用异或是判断两边是否不相等，不相等就表示有一个不为空，会返回false.
            if(node1.right == null ^ node2.right == null){
                return false;
            }
            if(node1.left == null ^ node2.left == null){
                return false;
            }
            if(node1.left != null){
                queue1.add(node1.left);
            }
            if(node1.right != null){
                queue1.add(node1.right);
            }
            if(node2.left != null){
                queue2.add(node2.left);
            }
            if(node2.right != null){
                queue2.add(node2.right);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }

    /**
     * @return 递归写法二
     */
    public boolean isSameTree3(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right) && p.val == q.val;
    }
    /**
     * @return 递归
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
        //如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，
        //若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，
        //因此可以使用深度优先搜索，递归地判断两个二叉树是否相同
        if(p == null && q == null){
            return true;
        }
        if(p != null && q != null){
            if(p.val == q.val){
                if(isSameTree(p.left,q.left) && isSameTree(p.right,q.right)){
                    return true;
                }
            }
        }
        return false;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
